# 17.电话号码的字母组合
# 给定一个仅包含数字2 - 9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
# 给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。
#
# 示例1：
# 输入：digits = "23"
# 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
#
# 示例2：
# 输入：digits = ""
# 输出：[]
#
# 示例3：
# 输入：digits = "2"
# 输出：["a", "b", "c"]


class Solution:
    def letterCombinations(self, digits: str):
        dic = {1:1, 2:['a','b','c'], 3:['d','e','f'],
               4:['g','h','i'], 5:['j','k','l'], 6:['m','n','o'],
               7:['p','q','r','s'], 8:['t','u','v'], 9:['w','x','y','z']}
        res = []
        path = []
        if not digits:
            return res
        def backtracking(digits,index):
            if len(digits) == index:
                tmp = "".join(path)
                res.append(tmp)
                return
            digit = int(digits[index])
            letter = dic[digit]
            for i in range(len(letter)):
                path.append(letter[i])
                backtracking(digits,index+1)
                path.pop()
        backtracking(digits,0)
        return res

if __name__ == '__main__':
    tmp = Solution()
    digits = "23"
    res = tmp.letterCombinations(digits)
    print(res)

